#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <windows.h>

#define MAX_SIZE 100

// 定义运算符栈
typedef struct {
    char data[MAX_SIZE];
    int top;
    int precedence[MAX_SIZE];
} Stack;

// 初始化栈
void initStack(Stack *s) {
    s->top = -1;
}

// 判断栈是否为空
bool isEmpty(Stack *s) {
    return s->top == -1;
}

// 判断栈是否已满
bool isFull(Stack *s) {
    return s->top == MAX_SIZE - 1;
}

// 入栈
void push(Stack *s, char value, int prec) {
    if (!isFull(s)) {
        s->data[++(s->top)] = value;
        s->precedence[s->top] = prec;
    } else {
        printf("栈已满，无法入栈。\n");
        exit(EXIT_FAILURE);
    }
}

// 出栈
char pop(Stack *s) {
    if (!isEmpty(s)) {
        return s->data[(s->top)--];
    } else {
        printf("栈为空，无法出栈。\n");
        exit(EXIT_FAILURE);
    }
}

// 获取栈顶元素
char peek(Stack *s) {
    if (!isEmpty(s)) {
        return s->data[s->top];
    } else {
        printf("栈为空，无法获取栈顶元素。\n");
        exit(EXIT_FAILURE);
    }
}

// 获取运算符优先级
int precedence(char op) {
    switch (op) {
        case '+':
        case '-':
            return 1;
        case '*':
        case '/':
            return 2;
        case '(':
            return 0; // 左括号的优先级最低
        default:
            return -1; // 其他字符返回-1
    }
}

// 将中缀表达式转换为后缀表达式
void infixToPostfix(char *infixExp, char *postfixExp) {
    Stack opStack;
    initStack(&opStack);
    push(&opStack, '=', -1); // 初始优先级设为-1

    char ch, topOp;
    int i = 0, j = 0;

    while ((ch = infixExp[i++]) != '\0') {
        if (ch >= '0' && ch <= '9') {
            postfixExp[j++] = ch;
            while (infixExp[i] >= '0' && infixExp[i] <= '9') {
                postfixExp[j++] = infixExp[i++];
            }
            postfixExp[j++] = '#'; // 以 '#' 结束一个数值
        } else {
            switch (precedence(ch)) {
                case 0: // 左括号
                    push(&opStack, ch, 0); // 优先级设为0
                    break;
                case 1:
                case 2:
                    while (precedence(peek(&opStack)) >= precedence(ch)) {
                        postfixExp[j++] = pop(&opStack);
                    }
                    push(&opStack, ch, precedence(ch)); // 将当前运算符和其优先级一同入栈
                    break;
                case -1: // 右括号
                    while (peek(&opStack) != '(') {
                        postfixExp[j++] = pop(&opStack);
                    }
                    pop(&opStack); // 弹出左括号
                    break;
                default:
                    printf("Error: Invalid operator.\n");
                    exit(EXIT_FAILURE);
            }
        }
    }

    while (!isEmpty(&opStack) && (topOp = pop(&opStack)) != '=') {
        postfixExp[j++] = topOp;
    }

    postfixExp[j] = '\0';
}

// 对后缀表达式求值
int evaluatePostfix(char *postfixExp) {
    Stack numStack;
    initStack(&numStack);

    int i = 0;
    char ch;
    int operand1, operand2;

    while ((ch = postfixExp[i++]) != '\0') {
        if (ch >= '0' && ch <= '9') {
            int num = 0;
            while (ch >= '0' && ch <= '9') {
                num = num * 10 + (ch - '0');
                ch = postfixExp[i++];
            }
            push(&numStack, num, -1); // 由于数字的优先级没有意义，这里将其设为-1
        } else {
            operand2 = pop(&numStack);
            operand1 = pop(&numStack);
            switch (ch) {
                case '+':
                    push(&numStack, operand1 + operand2, -1); // 结果入栈的优先级同样没有意义
                    break;
                case '-':
                    push(&numStack, operand1 - operand2, -1);
                    break;
                case '*':
                    push(&numStack, operand1 * operand2, -1);
                    break;
                case '/':
                    if (operand2 == 0) {
                        printf("Error: Division by zero.\n");
                        exit(EXIT_FAILURE);
                    }
                    push(&numStack, operand1 / operand2, -1);
                    break;
                default:
                    printf("Error: Invalid operator.\n");
                    exit(EXIT_FAILURE);
            }
        }
    }

    return pop(&numStack);
}

int main() {
    SetConsoleOutputCP(65001);
    char infixExp[MAX_SIZE];
    printf("请输入中缀表达式：\n");
    scanf("%s", infixExp);

    char postfixExp[MAX_SIZE];
    infixToPostfix(infixExp, postfixExp);
    printf("后缀表达式：%s\n", postfixExp);

    int result = evaluatePostfix(postfixExp);
    printf("表达式结果：%d\n", result);

    return 0;
}